1. Field of the Invention
The present invention relates, generally, to content delivery networks and, in preferred embodiments, to methods and apparatus for intelligent network bandwidth and system resource utilization for efficient web content fetching and refreshing.
2. Description of the Related Art
Web performance is a key point of differentiation among content providers. Snafus and slowdowns with major Web sites demonstrate the difficulties companies face when trying to scale large Web traffic. As Internet backbone technologies develop, many innovations, such as quality of service management, have been used to improve network bandwidth and improve Web content retrieval time. These improvements to infrastructure, however, cannot solve traffic problems occurring at any one point in the Internet. For example, in FIG. 1, an end user 10 in a network 12 in Japan wants to access a page in a content provider original Web site 14 in a network 16 in the U.S. The request will pass through several Internet Service Provider (ISP) gateways 18, 20, and 22 before it reaches the content provider original Web site 14. Because of gateway bottlenecks and other delay factors along the Internet paths between the user and the content provider original Web site 14, a content fetching and refreshing methodology utilizing a proxy server on the end user side of the gateways could provide faster response time.
FIG. 2 illustrates a typical Web content delivery and caching scheme 24 which includes a caching system 26 connected to multiple non-specific Web sites 28 and 30. The caching system 26 is comprised of a proxy server or cache server 32 and cache 34. Alternatively, the caching system 26 of FIG. 2 can be replaced by a content delivery services provider and mirror sites, which would be connected to Web sites that have entered into subscriber contracts with the content delivery services provider. These subscriber Web sites will deliver content to the content delivery services provider for mirroring, but will not necessarily notify the content delivery services provider when the content has changed. In addition, it should be understood that the cache 34 may be proxy cache, edge cache, front end cache, reverse cache, and the like.
In FIG. 2, when content is delivered from a Web site to cache 34, a header called a meta-description or meta-data is delivered along with the content. The meta-data may be a subset of the content, or it may indicate certain properties of the content. For example, the meta-data may contain a last-modified date, an estimate that the content will expire at a certain time, and an indication that the content is to expire immediately, or is not to be cached. After the content and meta-data are delivered, if storing the content in cache 34 is indicated by the meta-data, the content will be stored in cache 34.
When a user 36 (user 1) requests access to a page (e.g., index.html) from a Web site 28 (Web site 1), the Web browser of user 1 will first send a request to a domain name server (DNS) to find the Internet Protocol (IP) address corresponding to the domain name of Web site 1. If, as in the example of FIG. 2, a caching system 26 is employed, the Web browser may be directed to the proxy server 32 rather than Web site 1. The proxy server 32 will then determine if the requested content is in cache 34.
However, even though the requested content may be found in cache 34, it must be determined whether the content in cache 34 is fresh. This problem can be described as database synchronization. In other words, it is desirable for the cache 34 and Web site 1 to have content that is the same. As described above, however, subscriber Web sites may not notify the proxy server 32 when their content has changed. Thus, the proxy server 32 may examine the meta-data associated with the requested content stored in cache 34 to assist in determining of the content is fresh.
If the requested content is found in the cache 34 and the meta-data indicates that the estimated time for expiration has not yet occurred, some caching systems will simply deliver the content directly to the user 1. However, more sophisticated caching systems may send a request to Web site 1 for information on when the desired content was last updated. If the content was updated since the last refresh into cache 34, the content currently in the cache 34 is outdated, and fresh content will be delivered into the cache 34 from Web site 1 before it is delivered to the user 1. It should be understood, however, that this process of checking Web sites to determine if the content has changed will also increase bandwidth or system resource utilization.
Similarly, if the requested content is found in the cache 34 but the content was set to expire immediately, some caching systems will simply fetch the content from Web site 1 and deliver it to user 1. However, if the user requests a validation of data freshness, some caching systems may send a request to Web site 1 for information on when the desired content was last updated. If the content was last updated prior to the last refresh into cache 34, the content is still fresh and the caching system will deliver the content to user 1, notwithstanding the xe2x80x9cexpired immediatelyxe2x80x9d status of the content.
If the requested content is not in the cache 34, the proxy server 32 will send the request to Web site 1 to fetch the text of the desired Web page (e.g., index.html). After user 1""s Web browser receives index.html, the browser will parse the html page and may issue additional requests to Web site 1 to fetch any embedded objects such as images or icons. However, if a caching system 26 is employed, the proxy server 32 will first determine if the embedded objects are available in the cache 34. All traffic (i.e., data flow) is recorded in a log file 38 in the proxy server 32. The log file 38 may include the IP addresses of the location from which requests are issued, the URLs of objects fetched, the time stamp of each action, and the like. Note that a proxy server 32 is usually shared by many end users so that the content in the cache 34 can be accessed by users with similar interests. That is, if user 1 accesses a page and the page is stored in the cache 34, when another user 40 (user 2) requests the same page, the proxy server 32 can simply provide the content in the cache 34 to user 2.
In some caching systems a refresh may be performed even when there is no end user request for content. Without any user request being received, the cache will send a request to the Web site that delivered content into the cache to determine when the content in the Web site was last updated. If the content has changed, the content will be refreshed from the Web site back into cache. Thus, when a request for content is received from an end user, it is more likely that the content in cache will be fresh and transmitted directly back to the end user without further delay.
Network bandwidth resources and system resources are important for end users and proxy servers connected to the Internet. The end users and proxy servers can be considered to be xe2x80x9ccompetingxe2x80x9d with each other for bandwidth and connections resources, although their goals are the samexe2x80x94to provide users with the fastest response time.
FIG. 3 illustrates the connections available for a typical proxy server 42. The fastest response time for an individual request can be achieved when the requested content is located in the proxy server cache and is fresh, so that the proxy server 42 does not need to fetch the content from the Web site through the Internet. This situation is known as a cache xe2x80x9chit.xe2x80x9d System-wide, the fastest response times are achieved with a very high cache hit ratio. Thus, it would seem clear that more pre-fetching 44, refreshing, and pre-validation will lead to more fresh content, a higher cache hit ratio, and faster response times for an end user. However, there is a trade-off. To achieve a very high cache hit ratio, the proxy server 42 may need to utilize a high percentage of network bandwidth for content refreshing, pre-fetching, fetching, or pre-validation 44 into cache. Nevertheless, despite a large amount of refreshing, there will be occasions when an end user will request content that has not been refreshed into cache, or is simply not in the cache. In such a circumstance the proxy server 42 must issue a request fetch 46 to request the content from the Web site. However, if an excessive amount of bandwidth is currently being used to refresh other content, there may be insufficient bandwidth available for the cache to fetch the requested content from the Web site, and the response time of the content fetch may actually increase substantially. Thus, it should be understood that cache refreshing and pre-fetching competes with, and can be detrimental to, Web site content fetching.
Of course, if there is unused bandwidth at any moment in time, it makes sense to pre-fetch the highest priority content into cache so that it can be available for a requesting end user. For example, assume that 20% of the bandwidth is used for fetching content from a website when an end user requests the content and there is no cache hit. If 20% of the bandwidth is used for such fetches, then 80% of the bandwidth is unused. This unused bandwidth can be used to pre-fetch other content into cache so that when end users request that content it will be available to them.
Because of the competition between cache server refreshing and pre-fetching and Web site content fetching for network bandwidth, and the impact to user response time as a result of the allocation of bandwidth to these processes, a method for determining the optimum allocation of bandwidth for cache server refreshing and pre-fetching to yield the best response time is desired. Furthermore, if only a percentage of the content stored in cache can be refreshed or pre-fetched due to bandwidth limitations, a method for determining which content to be refreshed and pre-fetch in order to maximize the cache hit ratio and response time is also desired.
Therefore, it is an advantage of embodiments of the present invention to provide a method and apparatus for intelligent network bandwidth and system resource utilization for efficient web content fetching and refreshing that determines the optimum allocation of bandwidth for cache server refreshing and pre-fetching to yield the best end user response time.
It is a further advantage of embodiments of the present invention to provide a method and apparatus for intelligent network bandwidth and system resource utilization for efficient web content fetching and refreshing that determines the optimum allocation of bandwidth for cache server refreshing and pre-fetching to yield the best end user response time while accounting for fluctuations in available network bandwidth.
It is a further advantage of embodiments of the present invention to provide a method and apparatus for intelligent network bandwidth and system resource utilization for efficient web content fetching and refreshing that determines the optimum number of network connections for cache server refreshing and pre-fetching to yield the best end user response time.
It is a further advantage of embodiments of the present invention to provide a method and apparatus for intelligent network bandwidth and system resource utilization for efficient web content fetching and refreshing that determines the optimum number of network connections for cache server refreshing and pre-fetching to yield the best end user response time while accounting for fluctuations in available number of network connections.
It is a further advantage of embodiments of the present invention to provide a method and apparatus for intelligent network bandwidth and system resource utilization for efficient web content fetching and refreshing that determines which content should be refreshed and pre-fetched in order to maximize the cache hit ratio and response time.
These and other advantages are accomplished according to a content delivery services provider for directing the at least one proxy server to pre-fetch content from the at least one content provider original site using an optimum pre-fetch bandwidth allocation value. The content delivery services provider is part of a system for storing and delivering content, which includes a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content. These elements are coupled over a network for communicating with each other.
The content delivery services provider programmed for:
modeling a retrieval time of content o of size size(o) using b units of bandwidth as ret(o)=congestionxc3x97size(o)xc3x97d(b), wherein d(b) is a unit delay observed when b units of bandwidth is used for pre-fetching the content, and congestion(Util) can be represented as       congestion    (    Util    )    =            β                        Util          θ                +        α              +    φ  
or congestion(Util)=xcex2xc3x97(1.0xe2x88x92Util)xcex1+xcfx86;
modeling an amount of delay observed by the at least one proxy server for the content fetched from the at least one content provider original site at time t0 as             ret      ⁡              (        P        )              =                  congestion        (                              P            +                          r              ⁡                              (                                  t                  0                                )                                              B                )            xc3x97              r        ⁡                  (                      t            0                    )                    xc3x97      d        ,
wherein P is a pre-fetch bandwidth size, B is a total bandwidth available to the system, r(t)=(1xe2x88x92"sgr"(P))xc3x97u(t) is an amount of bandwidth the system uses for retrieving end user browser requests for content that is not stored in the at least one proxy server, "sgr"(P) is a cache freshness and availability value given a bandwidth P, and u(t) is a user access rate;
calculating the optimum pre-fetch bandwidth allocation value P by solving                     δ        ⁢                  xe2x80x83                ⁢                  ret          ⁡                      (            P            )                                      δ        ⁢                  xe2x80x83                ⁢        P              =    0    ;
and
communicating the optimum pre-fetch bandwidth allocation value P to the at least one proxy server.